題目：509. Fibonacci Number

連結：https://leetcode.com/problems/fibonacci-number/description/

• 等級：Easy

解題思路

1. temp1、temp2初始設定
2. 迴圈進行遞迴加總．

class Solution {
    public int fib(int n) {
        if (n == 0 || n==1)
            return n;
        int sum = 0;
        int temp1 = 0;
        int temp2 = 1;    
        for (int i = 2;i <= n;i++)
        {
            sum = temp1 + temp2;
            temp1 = temp2;
            temp2 = sum;
        }
        return sum;
    }
}

• Time complexity: O(n)
• Space complexity: O(n)

題目：42. Trapping Rain Water

連結：https://leetcode.com/problems/trapping-rain-water/description/

• 等級：Hard

解題思路

1. two point
2. Recursion

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = height[0], rightMax = height[height.length - 1];
        int water = 0;
        while (left < right) {
            if (leftMax < rightMax) {
                left++;
                if (leftMax < height[left]) {
                    leftMax = height[left];
                } else {
                    water += leftMax - height[left];
                }
            } else {
                right--;
                if (rightMax < height[right]) {
                    rightMax = height[right];
                } else {
                    water += rightMax - height[right];
                }
            }
        }
        return water;
    }
}

• Time complexity: O(n)
• Space complexity: O(1)